#include<iostream>
using namespace std;

int ans;

long long GCD(long long a, long long b){
	long long c = a % b;
	while(c){
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

void DFS(long long a, long long b, int dep){
	if(dep + 2 >= ans){
		return;
	}
	
	long long gcd = GCD(a, b);
	
	a /= gcd; b /= gcd;
	if(a == 1 || b == 1){
		ans = min(dep + 2, ans);
		return;
	}
	if(b % 2){
		swap(a, b);
	}
	
	DFS(a, b - 1, dep + 1);
	DFS(a - 1, b, dep + 1);
}
int main(){
	int T;
	long long a, b;
	
	cin >> T;
	for(int i = 0; i < T; i++){
		cin >> a >> b;
		ans = 100;
		DFS(a, b, 0);
		cout << ans << endl;
	}
	return 0;
}
